/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode *merge(ListNode *p1, ListNode *p2, ListNode *&lastNode) {
        if (p1==NULL) {
            lastNode=p2;
            while (lastNode!=NULL && lastNode->next!=NULL) lastNode=lastNode->next;
            return p2;
        }
        if (p2==NULL) {
            lastNode=p1;
            while (lastNode!=NULL && lastNode->next!=NULL) lastNode=lastNode->next;
            return p1;
        }
        ListNode guard(-1), *cur=&guard;
        while (p1!=NULL && p2!=NULL) {
            if (p1->val<p2->val) {
                cur->next=p1;
                cur=p1;
                p1=p1->next;
            } else {
                cur->next=p2;
                cur=p2;
                p2=p2->next;
            }
        }
        if (p1!=NULL) cur->next=p1;
        if (p2!=NULL) cur->next=p2;
        lastNode=cur;
        while (lastNode!=NULL && lastNode->next!=NULL) lastNode=lastNode->next;
        return guard.next;
    }

    ListNode *get(ListNode *&ptr, int n) {
        if (ptr==NULL) return NULL;
        ListNode *ret;
        ret=ptr;
        for (int i=0;i<n-1 && ptr->next!=NULL;i++) ptr=ptr->next;
        ListNode *tmp=ptr->next;
        ptr->next=NULL;
        ptr=tmp;
        return ret;
    }

public:
    ListNode *sortList(ListNode *head) {
        if (head==NULL) return NULL;
        ListNode guard(-1);
        guard.next=head;
        for (int x=1;;x*=2) {
            ListNode *p=guard.next;
            guard.next=NULL;
            ListNode *guardTail=&guard;
            bool more=true, outerNoMore=true, isFirst=true;
            while (p!=NULL && more) {
                ListNode *p1=get(p,x), *p2=get(p,x), *lastNode;
                if (p2==NULL) more=false;
                guardTail->next=merge(p1, p2, lastNode);
                guardTail=lastNode;
                if (isFirst && p2!=NULL) outerNoMore=false;
                isFirst=false;
            }
            if (outerNoMore) break;
        }
        return guard.next;
    }
};

